The present invention is directed to a finite field parallel multiplier. Multiplication of two elements in a finite field is needed in many applications including algebraic encoding and decoding of block codes, digital signal processing, pseudo-random number generation, and cryptographic protocols. A Reed-Solomon encoder and a Reed-Solomon decoder of the present invention make use of these finite field parallel multipliers.
Operations on finite field GF(q.sup.m) elements such as multiplication of one element by another element are well-known in the art. An element of GF(q.sup.m) is comprised of m components, each component having one of q possible values. Multiplication of two elements in a finite field can be done either serially or in parallel In a serial multiplier, the result of multiplication of two elements is obtained in multiple clock cycles (typically, m clock cycles). In a parallel multiplier the result of multiplication of two elements can be obtained in a single clock cycle. Thus, parallel multipliers are very useful when a high-speed implementation of an application is necessary. One implementation of a serial multiplication circuit can be found in E. R. Berlekamp, "Bit-Serial Reed-Solomon Encoders," IEEE Transactions on Information Theory, Vol. IT-28, No. 6, pp. 869-874, November 1982 Berlekamp discloses a multiplier circuit that is used m times to obtain the final product of two finite field elements. In the Berlekamp method, one of the elements is transformed from a standard basis to a dual basis before the multiplication can proceed. An improvement upon Berlekamp's method is disclosed in M. Morii et al., "Efficient Bit-Serial Multiplication and the Discrete-Time Weiner-Hopf Equation over Finite Fields," IEEE Transactions on Information Theory, Vol. 35, No. 6, pp. 1177-1183, November 1989 Morii et al. showed that there exist an entire set of bases that can be substituted for the dual basis used by Berlekamp.
The implementation of a parallel multiplier has required many times the number of gates than a serial multiplier. One implementation of a parallel multiplier can be found in C. W. Wang et al., "VLSI Architectures for Computing Multiplications and Inverses in GF(2.sup.m),"IEEE Transaction on Computers, Vol C-34, No. 8, pp. 709-717, August 1985. In the Wang et al. implementation, m function circuits each receive the same components from the two finite field elements differing in only that they have been shifted. The algorithm used by Wang et al. requires a large number of gates in the function circuits to determine the end result.
It is an object of the present invention to perform finite field multiplication in a single clock cycle. It is a further object of the present invention to provide a finite field multiplier that requires relatively few gates.